package JZ.JZ55;

/**
 * @author corn
 * @create 2020-07-31-14:58
 */

/**
 * JZ55 链表中环的入口结点
 * 题目描述
 * 给一个链表，若其中包含环，请找出该链表的环的入口结点，否则，输出null。
 */
public class EntryNodeOfLoop {

}
class Solution {

    public ListNode entryNodeOfLoop(ListNode pHead)
    {
        /*方法一：双指针：一个快指针，一个慢指针
                如果存在环，则慢指针一定会追上快指针，此时又让一个和慢指针一样速度的指针*/
        if(pHead == null || pHead.next == null){
            return null;
        }
        ListNode kHead = pHead;
        ListNode mHead = pHead;
        while (kHead != null && mHead != null){
            kHead = kHead.next.next;
            mHead = mHead.next;
            if(kHead.val == mHead.val){
                ListNode mHead2 = pHead;
                while (mHead != mHead2){
                    mHead = mHead.next;
                    mHead2 = mHead2.next;
                }
                return mHead;
            }
        }
        return null;
    }
}
class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}